package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_90 {

    private List<List<Integer>> res;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res = new ArrayList<>();
        res.add(new ArrayList<>());
        Arrays.sort(nums);
        dps(new ArrayList<>(), false, nums, 0);
        return res;
    }

    private void dps(List<Integer> list, boolean parent_contain, int[] nums, int index) {
        if (index < nums.length) {

            List<Integer> copy_old = new ArrayList<>(list);
            dps(copy_old, false, nums, index + 1);

            if (!parent_contain && index > 0 && nums[index] == nums[index - 1]) {
                return;
            }

            List<Integer> copy_new = new ArrayList<>(list);
            copy_new.add(nums[index]);
            res.add(copy_new);
            dps(copy_new, true, nums, index + 1);
        }
    }

    public static void main(String[] args) {
        Solution_90 model = new Solution_90();
                List<List<Integer>> lists = model.subsetsWithDup(new int[]{1, 2, 3});
        //        List<List<Integer>> lists = model.subsets(new int[]{0});
//        List<List<Integer>> lists = model.subsetsWithDup(new int[]{1, 2, 2});
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}
